import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;

public class Sort {
    //从小到大排序
    /*
    直接插入排序
    * 时间复杂度
    *  最好情况：数据完全有序：o(n)
    *  最坏情况：数据完全逆序o(n^2)
    * 空间复杂度：o(1)
    * 稳定性：稳定的排序
    * 一个稳定的排序可以实现为一个不稳定的
    * 但是一个不稳定不可能实现为一个稳定的
    * */
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >=0 ; j--){
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = tmp;重复了
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

 /*
    希尔排序（跳跃分组排序，是对直接插入排序的优化）
    * 时间复杂度
    *  一般在 n^1.3~n^1.6之间
    * 空间复杂度：o(1)
    * 稳定性：不稳定的排序
    * */
    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap >1){
            gap /= 2;
            shell (array , gap);
        }
        //因为在循环中不管gap原来是奇数还是偶数，都会计算gap = 1 的最后一次排序，所以不用额外写
        //shell(array,gap);
    }
    private static void shell(int[] array, int gap){
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (; j >=0 ; j-= gap){
                if(array[j] > tmp){
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }



   /*
    选择排序
    * 时间复杂度
    *  o(n^2)
    * 空间复杂度：o(1)
    * 稳定性：不稳定的排序
    * */


    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[minIndex]){
                    minIndex = j;
                }
            }
            swap(array,minIndex,i);
        }
    }

    private static void swap(int[] array,int i ,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void selectSort2(int[] array){
        int left = 0;
        int right = array.length-1;

        while(left < right){
            int minIndex = left;
            int maxIndex = left;

            for (int i = left+1; i <= right; i++) {
                if(array[i] < array[minIndex]){
                    minIndex =i ;
                }
                if(array[i] > array[maxIndex]){
                    maxIndex =i ;
                }
            }
            swap(array,left,minIndex);

            //最大值刚好在 left的位置 已经交换到了minIndex位置
            if(maxIndex == left){
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);

            left++;
            right--;
        }
    }


    /*
    堆排序
    *时间复杂度：o(n*logn)
    空间复杂度：o(1);
    稳定性:稳定的排序
    数据量非常大的时候，堆排会比希尔排序更快
    * */
    public static void heapSort(int[] array){
      createBigHeap(array);
      int end =array.length-1;
      while(end > 0) {
          swap(array, 0, end);
          siftDown(array, 0, end);
          end--;
      }
    }


    private static void createBigHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
            siftDown(array,parent,array.length);
        }
    }


    private static void siftDown(int[] array,int parent,int end){
        int child = (parent*2)+1;
        while(child < end){
            if(child+1 < end && array[child] < array[child+1]){
                child++;
            }

            if(array[parent] < array[child]){
                swap(array,parent,child);
                parent = child;
                child = (parent*2)+1;
            }else {
                break;
            }

        }
    }


    /**
     *冒泡排序
     * 时间复杂度：不优化o(n^2)
     * 最好情况:o(n)
     * 空间复杂度:o(1)
     *
     */
    public static void bublleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            //因为不一定要比较全部长度的次数
            boolean flg =false;
            //j < array.length-1-i; 每次都少比较一次比 j < array.length-1更快
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]){
                    swap(array,j,j+1);
                    //如果一趟走完发生交换，把flg置为true
                    flg =true;
                }
            }
            //如果为false说明没有发生交换，已经有序了，直接return
                if(flg == false){
                    return;
            }
        }
    }


    /**
     *  Hoare法快速排序
     * 时间复杂度：
     *      最好情况:
     *              O(N*logN)   满二叉树/完全二叉树
     *      最坏情况:
     *            O(N^2) 单分支的树
     * 空间复杂度：
     *   最好情况:
     *           O(logN)   满二叉树/完全二叉树
     *  最坏情况:
     *          O(N)   单 分支的树
     * 稳定性：不稳定
     * @param array
     */
    public static void quickSort(int[] array){
        int start = 0;
        int end = array.length-1;
        quick(array,start,end);
    }


    private static void quick(int[] array,int start,int end){

        //结束条件,这时候说明左边只有一个节点或者一个节点都没有了
        if(start >= end) return;

        //在这个区间内使用插入排序来提升效率,小区间的插入排序减少递归的次数
        if(end - start <= 15){
            insertSortRange(array,start,end);
            return;
        }


        //三数取中法（优化快速排序）
        int index = midOfIndex(array,start,end);
        swap(array,index, start);//此时交换完成之后 一定能过保证start下标 是中间大的数字

         int pivot = partitionHoare(array,start,end);
         quick(array,start,pivot-1);
         quick(array,pivot+1,end);


    }
    //快速排序里面的插入排序
    private static void insertSortRange(int[] array,int begin ,int end){
        for (int i = begin+1; i <= end; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >=begin ; j--){
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = tmp;重复了
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    //三数取中法（，三数取中并不能保证每次都准确地找到中间大小的值，只是一种优化策略）
    private static int midOfIndex(int[] array, int left, int right) {
        int mid = (left + right)/2;
        //左小于右
        if(array[left] < array[right]){
            if(array[left] > array[mid]){
                return left;
            } else if (array[right] > array[mid]) {
                return mid;
            }else {
                return right;
            }

        }else {  //左大于右
            if(array[left] < array[mid]){
                return left;
            } else if (array[right] > array[mid]) {
                return right;
            }else {
                return mid;
            }
        }
    }


    private static int partitionHoare(int[] array, int left, int right){

        int key = array[left];
        int i = left;
        while (left < right) {
            //一定要先让right--,再让left++
            while (left < right && array[right] >= key) {//这里为什么要取等号
                right--;
            }
            //right 下标一定是 比key小的数据
            while (left < right && array[left] <= key) {//这里为什么要取等号
                left++;
            }
            //left 下标一定是 比key大的数据

            swap(array,left,right);
        }
        //相遇的位置 和 i（初始的位置） 位置进行交换,这里写left或right都可以
        swap(array,left,i);

        return left;
    }



    //挖坑法
    private static int partitionWaKen(int[] array, int left, int right){

        int key = array[left];
        while (left < right) {
            //一定要先让right--,再让left++
            while (left < right && array[right] >= key) {//这里为什么要取等号
                right--;
            }
            array[left]  = array[right];
            //right 下标一定是 比key小的数据
            while (left < right && array[left] <= key) {//这里为什么要取等号
                left++;
            }
            //left 下标一定是 比key大的数据
            array[right]  = array[left];

        }
        //相遇的位置 和 i（初始的位置） 位置进行交换,这里写left或right都可以
        array[right] = key;

        return left;
    }



    //前后指针法
    private static int partition(int[] array, int left, int right) {
        int prev = left ;
        int cur = left+1;
        while (cur <= right) {
            //这里会 拉开prevhecur的距离
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }


    //快速排序(非递归)
    public static void quickSortNor(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;

        int pivot = partition(array,left,right);
        //说明左边至少还有两个对象
        if(pivot - 1 >left){
            stack.push(left);
            stack.push(pivot - 1);
        }
        //说明左边至少还有两个对象
        if(pivot + 1 < right){
            stack.push(pivot + 1);
            stack.push(right);
        }

        while(! stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
             pivot = partition(array,left,right);
            //说明左边至少还有两个对象
            if(pivot - 1 >left){
                stack.push(left);
                stack.push(pivot - 1);
            }
            //说明左边至少还有两个对象
            if(pivot + 1 < right){
                stack.push(pivot + 1);
                stack.push(right);
            }
        }

    }





    /**
     * 归并排序
     * 时间复杂度： 0(N*logN)
     * 空间复杂度：O(n)
     * 稳定性: 稳定
     *      插入排序   冒泡    归并
     * @param array
     */
    public static void mergeSort(int[] array) {
        mergeSortFunc(array,0,array.length-1);
    }


    //分解
    private static void mergeSortFunc(int[] array, int left, int right) {
        //直到子数组的长度为 1 （left >= right）。
        if(left >= right) return;
        int mid =(left + right) / 2;

        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);

        //归并排序
        merge(array,left,right,mid);
    }

    private static void merge(int[] array, int left, int right, int mid) {
        int s1 = left;
        int s2 = mid+1;

        //存入到一个临时的数组中
        int[] tmparr = new int[right - left +1];
        //tmparr 的下标
        int k = 0;

        //保证两组中都有数据
        while (s1 <= mid && s2 <= right) {
            if (array[s1] < array[s2]) {
                tmparr[k] = array[s1];
                k++;
                s1++;
            }else {
                tmparr[k] = array[s2];
                k++;
                s2++;
            }
        }

        //判断第一个数组没有走完
        while(s1 <= mid){
            tmparr[k] = array[s1];
            k++;
            s1++;
        }

        while(s2 <= right){
            tmparr[k] = array[s2];
            k++;
            s2++;
        }

        //tmpArr 里面一定是这个区间内有序的数据了,并且把tmparr里的数据全部放回array
        for (int i = 0; i < tmparr.length; i++) {
            array[i+left] = tmparr[i];
        }

    }



    //归并排序的非递归
    public static void mergeSortNor(int[] array) {
        int gap = 1;
        while(gap < array.length){
            for (int i = 0; i < array.length; i+= 2*gap) {
                int left = i;
                int mid = left+gap-1;
                int right = mid + gap;

                //mid和right 可能会越界
                if(mid >= array.length){
                    mid = array.length-1;
                }

                if(right >= array.length){
                    right = array.length-1;
                }

                merge(array,left,right,mid);
            }
            gap*=2;
        }

    }



    //计数排序，适用于一个区间内大量出现的数字
    /**
     * 时间复杂度：
     * O(N+数据的范围)
     * 空间复杂度：O(数据的范围)
     * 稳定性：
     *
     * 计数排序 和 你给定的 范围有关系
     * @param array
     */
    public static void countSort(int[] array){
        int minVal = array[0];
        int maxVal = array[0];
        //找到数组中的最大值和最小值
        for (int i = 1; i < array.length; i++) {
            if(array[i] < minVal) {
                minVal = array[i];
            }
            if(array[i] > maxVal) {
                maxVal = array[i];
            }
        }

        //申请一个计数数组
        int[] count = new int[maxVal - minVal+1];

        //遍历原数组将数据加入count,开始计数
        for (int i = 0; i < array.length; i++) {
            //当前下标数量+1 比如最小值是90 当前值为91 1下标位置++
            count[array[i]-minVal]++;
        }

        //4、遍历计数cout 把 当前元素 写回 array
        int index = 0;//重新表示array数组的下标
        for (int i = 0; i < count.length; i++) {
            while(count[i] > 0){//说明一个数字还没有走完
                array[index] = i + minVal;
                index++;
                count[i]--;
            }
        }
    }




    /**
     * 基数排序
     * 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9
     */

        public int[] sort(int[] sourceArray) throws Exception {
            // 对 arr 进行拷贝，不改变参数内容
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

            int maxDigit = getMaxDigit(arr);
            return radixSort(arr, maxDigit);
        }

        /**
         * 获取最高位数
         */
        private int getMaxDigit(int[] arr) {
            int maxValue = getMaxValue(arr);
            return getNumLenght(maxValue);
        }

        private int getMaxValue(int[] arr) {
            int maxValue = arr[0];
            for (int value : arr) {
                if (maxValue < value) {
                    maxValue = value;
                }
            }
            return maxValue;
        }

        protected int getNumLenght(long num) {
            if (num == 0) {
                return 1;
            }
            int lenght = 0;
            for (long temp = num; temp != 0; temp /= 10) {
                lenght++;
            }
            return lenght;
        }

        private int[] radixSort(int[] arr, int maxDigit) {
            int mod = 10;
            int dev = 1;

            for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
                // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
                int[][] counter = new int[mod * 2][0];

                for (int j = 0; j < arr.length; j++) {
                    int bucket = ((arr[j] % mod) / dev) + mod;
                    counter[bucket] = arrayAppend(counter[bucket], arr[j]);
                }

                int pos = 0;
                for (int[] bucket : counter) {
                    for (int value : bucket) {
                        arr[pos++] = value;
                    }
                }
            }

            return arr;
        }

        /**
         * 自动扩容，并保存数据
         *
         * @param arr
         * @param value
         */
        private int[] arrayAppend(int[] arr, int value) {
            arr = Arrays.copyOf(arr, arr.length + 1);
            arr[arr.length - 1] = value;
            return arr;
        }



    public static void bucketSort(int[] arr){

        // 计算最大值与最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length; i++){
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }

        // 计算桶的数量
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i = 0; i < bucketNum; i++){
            bucketArr.add(new ArrayList<Integer>());
        }

        // 将每个元素放入桶
        for(int i = 0; i < arr.length; i++){
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }

        // 对每个桶进行排序
        for(int i = 0; i < bucketArr.size(); i++){
            Collections.sort(bucketArr.get(i));
        }

        // 将桶中的元素赋值到原序列
        int index = 0;
        for(int i = 0; i < bucketArr.size(); i++){
            for(int j = 0; j < bucketArr.get(i).size(); j++){
                arr[index++] = bucketArr.get(i).get(j);
            }
        }
    }



}
